#include "LinkTree.h"

#include <stdio.h>
#include <stdlib.h>

//树的节点
struct TreeNode
{
    TreeElementType data;
    //双亲节点
    struct TreeNode *parent;
    //孩子节点列表
    DLlist childs;
};

//树结构体
struct LinkTree
{
    //树的根
    TNode *root;
};

TNode *CreateTreeNode(TreeElementType element)
{
    TNode *newNode = (TNode*)malloc(sizeof(TNode));
    if(newNode == NULL)
    {
        printf("create tree error!\n");
        return NULL;
    }
    newNode->data = element;
    newNode->parent = NULL;
    InitDLlist(&newNode->childs); 
    return newNode; 
}

void FreeTreeNode(void *n)
{
    TNode *freeNode = (TNode*)n;
    if(freeNode == NULL)
        return;
    //先递归释放子节点们,最后再释放自己
    ClearDLlist(&freeNode->childs,FreeTreeNode);
    free(freeNode);
}

void *GetTreeNodeData(TNode *node)
{
    return node->data;
}

void ConnectBranch(TNode *parent, TNode *child)
{
    //判断节点是否为空
    if(parent == NULL || child == NULL)
        return;
    
    child->parent = parent;
    InsertDLlistTail(&parent->childs,child);
}


//回调函数
bool IsNodeEqual(void *ptr1,void *ptr2)
{
    //链表里的节点
    TNode *node1 = (TNode*)ptr1;
    //要删除的节点
    TNode *node2 = (TNode*)ptr2;

    return node1 == node2;
}

void DisconnectBranch(TNode *parent, TNode *child)
{
    //判断节点是否为空
    if(parent == NULL || child == NULL)
        return;

    //判断child是否为parent的孩子
    if(child->parent != parent)
    {
        printf("两个节点不是父子关系!\n");
        return;
    }

    child->parent = NULL;
    RemoveByElement(&parent->childs,child,IsNodeEqual,NULL);
}

void TravelTreeNode(TNode *node, int deepth, void (*funcPtr)(void *))
{
    if(node == NULL || funcPtr == NULL)
        return;

    if(node->parent != NULL)
    {
        //先打印自己
        for(int i = 0; i < deepth; i++)
            printf("    ");
        if(deepth >= 1)
            printf("|__");
        funcPtr(node->data);
    }
       

    //打印所有的孩子
    DLNode* TravelPoint = node->childs.head;
    while(TravelPoint->next != NULL)
    {
        TravelTreeNode((TNode*)TravelPoint->next->data,deepth + 1,funcPtr);
        TravelPoint = TravelPoint->next;
    }
}

TNode *FindChildNode(TNode *parent, void *value, bool (*funcPtr)(void *, void *))
{
    DLNode* TravelPoint = parent->childs.head;
    while(TravelPoint->next != NULL)
    {
        TNode *child = (TNode*)TravelPoint->next->data;
        if(funcPtr(child->data,value) == true)
        {
            return child;
        }
        TravelPoint = TravelPoint->next;
    }
    return NULL;
}

LTree *InitLinkTree()
{
    LTree *tree = (LTree*)malloc(sizeof(LTree));
    if(tree == NULL)
    {
        printf("crete tree error!\n");
        return NULL;
    }

    tree->root = CreateTreeNode(NULL);
    return tree;
}

TNode *GetTreeRoot(LTree *tree)
{
    return tree->root;
}

int GetNodeHight(TNode *node)
{
    if(node == NULL)
        return 0;

    int height = 0;
    DLNode* TravelPoint = node->childs.head;
    while(TravelPoint->next != NULL)
    {
        int childHeight = GetNodeHight((TNode*)TravelPoint->next->data);
        //取最大的
        height = height > childHeight ? height : childHeight;
        TravelPoint = TravelPoint->next;
    }
    return height + 1;
}

int GetTreeHeight(LTree *tree)
{
    //不带根节点就-1
    return GetNodeHight(tree->root) - 1;
}

void TravelTree(LTree *tree, void (*funcPtr)(void *))
{
    TravelTreeNode(tree->root,-1,funcPtr);
}

TNode *FindTreeNode(TNode *node,void* value,bool (*funcPtr)(void *, void *))
{
    //终止条件
    if(node == NULL || funcPtr == NULL)
        return NULL;
    
    //符合条件(排除根节点)
    if(node->parent != NULL && funcPtr(node->data,value) == true)
    {
        return node;
    }

    //不符合条件
    TNode *tragetNode = NULL;
    DLNode* TravelPoint = node->childs.head;
    while(TravelPoint->next != NULL)
    {
        tragetNode = FindTreeNode((TNode*)TravelPoint->next->data,value,funcPtr);
        //在孩子节点找到
        if(tragetNode != NULL)
        {
            return tragetNode;
        }
        TravelPoint = TravelPoint->next;
    }
    return tragetNode;
}

TNode *FindLinkTreeNode(LTree *tree, void *value, bool (*funcPtr)(void *, void *))
{
    return FindTreeNode(tree->root,value,funcPtr);
}

void FindAllLF(TNode *node,DLlist *list)
{
    //终止条件
    if(node == NULL)
        return;
    
    //node本身是叶子
    if(node->childs.len == 0)
    {
        InsertDLlistTail(list,node);
    }

    DLNode* TravelPoint = node->childs.head;
    while(TravelPoint->next != NULL)
    {
        FindAllLF((TNode *)TravelPoint->next->data,list);
        TravelPoint = TravelPoint->next;
    }
}

DLlist FindAllLeafBranches(LTree *tree)
{
    INITDLLIST(list);

    FindAllLF(tree->root,&list);
    return list;
}

void ClearLinkTree(void *tree)
{
    if(tree == NULL)
        return;
    LTree *tp = (LTree*)tree;
    FreeTreeNode(tp->root);
    free(tp);
}

